package top;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 *
 * 至少有k个重复字符的最长子串： 分治法
 *
 * @author chenyw
 * @date 2022/7/22 16:49
 */
public class Top395longestSubstring {
    public int longestSubstring(String s, int k) {
        int n = s.length();
        return dfs(s, 0, n - 1, k);
    }

    private int dfs(String s, int l, int r, int k) {
        int[] arr = new int[26];
        //找数量小于k的字符，以它为节点进行切割
        for (int i = l; i <= r; i++) {
            arr[s.charAt(i) - 'a']++;
        }
        char split = 0;
        for (int i = 0; i < 26; i++) {
            if (arr[i] > 0 && arr[i] < k) {
                split = (char) (i + 'a');
                break;
            }
        }
        if (split == 0) {
            return r - l + 1;
        }
        //分治
        int i = l;
        int j = r;
        int res = 0;
        while (i <= j) {
            while (i <=j && s.charAt(i) == split) {
                i++;
            }
            if (i > j) {
                break;
            }
            int start = i;
            while (i <= j && s.charAt(i) != split) {
                i++;
            }
            int length = dfs(s, start, i - 1, k);
            res = Math.max(length, res);

        }
        return res;
    }
}
